package dp.剑指;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 剑指Offer42连续子数组的最大和.java
 * @Description https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
 * @createTime 2021年12月11日 15:16:00
 *
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 *
 * 要求时间复杂度为O(n）
 */
public class 剑指Offer42连续子数组的最大和 {
	public int maxSubArray(int[] nums) {

		int length = nums.length;
		//定义dp[i] 表示到位置i 子数组的值之和
		int[] dp=new int[length];

		//初始化
		dp[0]=nums[0];

		int max=dp[0];

		/**
		 * dp[i]的值 = dp[i-1]+nums[i]
		 *  状态:dp[i]:以第i个数结尾的和的最大值
		 *  转移:若dp[i - 1] < 0,则以第i个数结尾的和的最大值为第i个数本身
		 *      若dp[i - 1] > 0,则以第i个数结尾的和的最大值为的dp[i - 1]与dp[i - 1] + nums[i]中的较大者
		 *  避免遍历dp数组，每次比较dp更新结束后比较res与dp[i]的大小作为返回值
		 *
		 */
		for (int i = 1; i < length; i++) {
			dp[i] = dp[i-1] > 0 ? dp[i-1]+nums[i] : nums[i];
			max = Math.max(max, dp[i]);
		}
		return max;
	}

	public int maxSubArray2(int[] nums) {
		int length = nums.length;

		int max=Integer.MIN_VALUE;

		int pre=0;

		for (int num : nums) {
			pre=Math.max(pre,pre+num);
			max=Math.max(pre,max);
		}
		return max;
	}
}
